package main

import "fmt"

func main() {
	n := 3
	fmt.Println(generateParenthesisByRecursion(n))
}

var result []string

//通过递归生成括号
func generateParenthesisByRecursion(n int) []string {
	result = make([]string, 0)
	generate(make([]byte, 2*n), 0)
	return result
}

func generate(curr []byte, post int) {
	//当已添加的字符与目标长度相等时
	if len(curr) == post {
		//判断是否有效
		if isValid(curr) {
			result = append(result, string(curr))
		}
	} else {
		curr[post] = '('
		generate(curr, post+1)
		curr[post] = ')'
		generate(curr, post+1)
	}
}

func isValid(curr []byte) bool {
	leftLen := 0
	for _, letter := range curr {
		switch letter {
		case '(':
			leftLen++
		default:
			leftLen--
		}
		if leftLen < 0 {
			return false
		}
	}
	return leftLen == 0
}
